Zwiedzanie miasta
Limit pamięci: 32 MB
Bajtocka Agencja Turystyczna (w skrócie BAT) chce wejść na rynek
oferując zwiedzanie Bajtogrodu autobusem-kabrioletem.
Należy zbudować siedzibę firmy, w której
będzie się zaczynało i kończyło zwiedzanie.
Trasa zwiedzania musi przechodzić wszystkimi ulicami miasta,
w przeciwnym przypadku turyści mogliby podejrzewać, że nie zobaczyli
czegoś bardzo interesującego.
Ulice nie muszą być proste i mogą przebiegać tunelami lub wiaduktami.
Wszystkie ulice są dwukierunkowe.
Każda ulica łączy dwa skrzyżowania.
Z każdego skrzyżowania w czterech kierunkach wychodzą ulice.
Może się zdarzyć, że dwa skrzyżowania są połączone więcej niż jedną ulicą.
Na ulicach nie wolno zawracać, ale można to robić na skrzyżowaniach.
Ponadto wiadomo, że z każdego skrzyżowania da się dojechać do każdego innego.
Przy każdej ulicy, dokładnie w połowie drogi pomiędzy
skrzyżowaniami, które łączy ulica, znajduje się szczególnie godna
podziwu atrakcja turystyczna
(np. piękny widok, pomnik lub inny zabytek),
wywierająca na zwiedzających "wrażenie" określone nieujemną
liczbą całkowitą.
Siedziba BATu powinna znajdować się przy jednej z takich atrakcji.
Przy doborze trasy zwiedzania należy brać pod uwagę zainteresowanie
turystów, które może się zmieniać w trakcie zwiedzania.
Przejechanie autobusem jednej bajtomili powoduje
spadek zainteresowania o jeden.
Przejechanie po raz pierwszy obok danej atrakcji
turystycznej zwiększa
zainteresowanie turystów, o liczbę określająca wrażenie, jakie
robi atrakcja.
Początkowo poziom zainteresowania turystów jest równy
wrażeniu, jakie robi atrakcja,
przy której znajduje się siedziba BATu.
Zainteresowanie turystów nie może w trakcie wycieczki nigdy spaść poniżej zera.
Zadanie
Napisz program, który:
- wczyta opis miasta ze standardowego wejścia,
- znajdzie trasę spełniającą podane wymagania, lub
stwierdzi, że taka trasa nie istnieje,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się
jedna liczba całkowita określająca liczbę skrzyżowań,
.
Skrzyżowania są ponumerowane od 1 do , a ulice są
ponumerowane od 1 do .
Kolejnych wierszy opisuje ulice -
-szy wiersz w pliku opisuje ulicę o numerze .
W każdym wierszu znajdują się cztery liczby całkowite
, , , oddzielone pojedynczymi odstępami.
Liczby i to numery skrzyżowań, które łączy
dana ulica, , .
Liczba jest parzystą liczbą całkowitą będącą długością ulicy w
bajtomilach, .
Atrakcja turystyczna położona przy danej ulicy robi wrażenie
określone liczbą , .
Wyjście
W pierwszym wierszu standardowego wyjścia wypisz
jedno słowo TAK, jeżeli istnieje taka trasa,
lub NIE, w przeciwnym przypadku.
Jeśli odpowied"z jest pozytywna to kolejne
wiersze powinny opisywać przykładową trasę.
Drugi wiersz powinien zawierać dokładnie jedną liczbę
całkowitą równą liczbie skrzyżowań występujących na
trasie zwiedzania.
(Pamiętaj, że ulica, przy której ma znajdować się siedziba BATu łączy
pierwsze i ostatnie skrzyżowanie).
Oznaczmy przez (dla ) numer
ulicy, którą podczas zwiedzania dojeżdża się do -tego
(w kolejności zwiedzania) skrzyżowania.
Kolejny wiersz powinien zawierać dwie liczby
całkowite i równe odpowiednio
numerowi ulicy, przy której należy zbudować siedzibę BATu
oraz numerowi pierwszego skrzyżowania, przez które prowadzi trasa
zwiedzania.
Kolejne wierszy powinno zawierać po jednej liczbie
całkowitej, odpowiednio , , , .
Przykład
Dla danych wejściowych:
4
1 2 4 6
2 4 2 4
3 2 4 2
4 3 10 8
2 1 8 7
4 3 2 1
1 4 2 6
3 1 4 5
poprawną odpowiedzią jest:
TAK
8
5 2
2
6
3
1
8
4
7
Autor zadania: Krzysztof Onak.